package 校招笔试.百度笔试;

import org.junit.Test;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/3/8 16:42
 */
public class 排列的个数 {

    /*
     小红拿到了一个排列，她想知道有多少区间满足，区间内部的数构成一个排列？
排列的定义：1到k，每个数都出现过且恰好出现一次，被称为一个长度为k的排列。例如[2,1,3],[4,3,2,1]都是排列。
输入描述：
有多组数据，首先输入一个正整数T，表示有T组数据（1<=T<=2）。
每组数据的第一行输入一个正整数n，代表排列的大小（1<=n<=2*10e5）。
每组数据的第二行输入n个正整数

输入示例
2
5
1 2 3 4 5
5
2 1 5 3 4
输入示例
5
3
说明
第一章数据，[1],[1,2],[1,2,3],[1,2,3,4],[1,2,3,4,5]共5个排列。
第二组数据，[2,1],[1],[2,1,5,3,4]共3个排列。

作者：杨
链接：https://leetcode.cn/circle/discuss/6oUmSd/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */






    /*

    思路 有点 偏差, 但是 有点 接近, ( 不应该 用 等差数列 求和, 而应该 用  排列 中 最大值 与最小值  的差值 与 项数 之间的对应关系 即可! )
    ==
    创建一个 新的 数组 index[]
     遍历 数组, 将 数组中的 元素 的 所造的 索引 idx 存入 index[]中
     如果 区间 下标 [1,i] 能构成 一个 排列 那么 ,sum(index[1],index[i]) 符合 等差数列 求和 公式
     则 等式 为 sum(index[1], index[k]) = kx + k(k - 1) / 2 .  (x 是 等差数列的首项 值 ,也就是 1 对应的 index 值, k 是项数)
     */
    public int solution(int nums[]){
        int index[] = new int[nums.length + 1] ,ans = 0,sum = 0;
        for(int i = 0;i < nums.length;i++){
            index[nums[i]] = i;
        }
        int min = index[1],max = index[1];
        for(int i = 1;i < index.length;i++){
            min = Math.min(index[i],min);
            max = Math.max(max,index[i]);
            sum += index[i];
//            ans += sum == i * index[1] + i * (i - 1) / 2 ? 1 : 0;
            //( 首项 + 尾项 ) * 项数 / 2
            ans += sum == (max + min) * i / 2 ? 1 : 0;
        }
        return ans;
    }
    @Test
    public void test(){
        int nums[] = {3,1,2};
        int nums1[] = {2,1,5,3,4};
        System.out.println(solutionRight(nums));
        System.out.println(solutionRight(nums1));
    }




    /*
     i从1到n，维护1~i这些数下标的最小值a和最大值b，如果b-a+1==i，则构成了一个排列
     这个 思路 是正确的 :
     排列 : 排列中的 max - min = 排列的 项数  - 1
     而这里的 排列要求的 更加 严格 , 必须 以 1 开头的 排列
     eg : 2 ,1 ,5 , 3 , 4
          0  1  2   3   4
        max - min = 4 - 0 = 项数  - 1 = 4
        注意 该题中的 max 和 min 全部代指的 是 下标
     就是上面的 例子!
     */




/*
该题主要 还是一些 数学 知识的应用!
  O(N)  O(N)
  评论区 好像有个  空间复杂度 O (1)
  的算法

  ==

  也可以下面 按照 下面 这样写, 反正最终的 结果就是, 得到 一个 index[] ,(明白 index  数组 的 含义!)
  Arrays.sort(index,(a,b) -> nums[a] - nums[b]); 这样的话,时间复杂度 就是 O(N* logN)
 */
    public int solutionRight(int nums[]){
                    // 元素 1 ~ n 元素的 下标 映射数组
        int ans = 0 ,index[] = new int[nums.length + 1];
        for(int  i = 0;i < nums.length;i++){
            index[nums[i]] = i;
        }
        int max = index[1],min = index[1];
        for(int i = 1;i < index.length; i++){
            max = Math.max(max,index[i]);
            min = Math.min(min,index[i]);
            ans += max - min == i - 1 ? 1: 0;
        }
        return ans;
    }

}
